package leetcode;

/**
 * 279. 完全平方数
 * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 * <p>
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 * 示例 2：
 * <p>
 * 输入：n = 13
 * 输出：2
 * 解释：13 = 4 + 9
 *
 * TODO 不是很理解
 */
public class NumSquares {

    public int numSquares(int n) {

        // dp[i] 表示最少需要多少个完全平方数相加等于i。比如 i = 13，则需要4 + 9
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {

            dp[i] = i; // 最坏的情况就是每次+1 比如: dp[3]=1+1+1

            for (int j = 1; i - j * j >= 0; j++) { // 枚举前一个状态
                // i_pre 越来越小
                // i_pre 加一个 完全平方数等于 i
                int i_pre = i - j * j;
                dp[i] = Math.min(dp[i], dp[i_pre] + 1);
            }
        }
        return dp[n];

    }

}
